/**
 * 188. 买卖股票的最佳时机 IV
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
 */
public class Solutions_188 {
    public static void main(String[] args) {
//        int k = 2;
//        int[] prices = {2, 4, 1};  // output: 2

        int k = 2;
        int[] prices = {3, 2, 6, 5, 0, 3};  // output: 7

        int result = maxProfit(k, prices);
        System.out.println(result);
    }

    /**
     *      第一次买    第一次卖    第二次买   第二次卖
     * 3      -3         0         -3        0
     * 2      -2         0         -2        0
     * 6      -2         4         -2        4
     * 5      -2         4         -1        4
     * 0       0         4          4        4
     * 3       0         4          4        7
     * 若 k 大于等于数组的一半，即可以任意买卖，套用 122 题解法
     * 否则需要在 k 笔交易中计算出最大利润，套用 123 题解法
     */
    public static int maxProfit(int k, int[] prices) {
        int days = prices.length;
        if (days < 2 || k < 1) {
            // 条件判断：天数小于 2 时无法买卖 或者 k 小于 1 时不允许交易
            return 0;
        }
        // {3, 2, 6, 5, 0, 3} 中，最多也只能进行 3 次交易
        k = Math.min(k, (days + 1) / 2);
        // k 笔交易共有买卖 op 次
        int op = k * 2;
        int[][] dp = new int[days][op];
        // 计算出第 i 天时，4 种状态下可获得的最大利润
        for (int i = 0; i < prices.length; i++) {
            for (int j = 0; j < op; j += 2) {
                if (i == 0) {
                    dp[0][j] = -prices[0];
                    continue;
                }
                int profit = 0;
                if (j > 0) {
                    profit = dp[i - 1][j - 1];
                }
                // 第 k 次买入
                dp[i][j] = Math.max(dp[i - 1][j], profit - prices[i]);
                // 第 k 次卖出
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
            }
        }
        return dp[days - 1][op - 1];
    }
}
